COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	∂14-Mar-79  1832	PRATT at MIT-AI (Vaughan Pratt)    
C00027 ENDMK
C⊗;
∂14-Mar-79  1832	PRATT at MIT-AI (Vaughan Pratt)    
Date: 14 MAR 1979 2131-EST
From: PRATT at MIT-AI (Vaughan Pratt)
To: jra at SU-AI
CC: PRATT at MIT-AI

Ok, here at long last is a 100% complete version of my paper.  Any follow-on
versions will have to be at least 101% complete.  Provided Byte is agreeable
to my putting out an AI Lab report with the same content, and provided they
get my approval of editorial changes, they henceforth have my blessings for
publishing the thing this year.




			 LISP - A Mathematician's View

				 Vaughan Pratt
				    M.I.T.


	All higher order languages offer the programmer mechanisms for
simplifying and clarifying programs.  Viewed from the distance that
mathematicians such as myself prefer, away from the distractions of detail,
Lisp stands out as the first language to pay serious attention to the following
issues.

	Mobility of data.
	Modularity of function.
	Declarative programming.
	Metalinguistics (the ability of a language to talk about language).

	Since the development of Lisp two other languages, APL and (to a lesser
extent) Snobol, have joined Lisp in dealing with at least some of these issues.
As such one would assume that they would have improved on Lisp.  We argue that
Lisp outclasses these languages despite its having been developed earlier.
Other languages such as Fortran, Basic, Algol, PL/I, and Pascal (or FBAPP as
Professor Alan Perlis of Yale University refers to them collectively) are in
Perlis's opinion and mine not in the same class as Lisp and APL with respect to
the issues discussed here.  (I do not know Alan's opinion of Snobol.)

1.  Mobility of data

	In a computer, data flows between three major classes of sites:
storage, functions, and devices.  Storage consists of registers and main memory
in assembly language, variables (simple and subscripted) in higher level
languages.  Functions (or procedures, or subroutines) are pretty much the same
in all languages, to within minor technical distinctions.  Typical devices are
printers, keyboards, floppies, paper tape readers, and the like.

	The corresponding mechanisms available to the programmer for expediting
this flow of data are fetch and store instructions, parameter-passing and
value-returning constructs, and read and write commands.  A mobile datum is one
which can be moved from one to site to another by the program with a minimum of
fuss.

	To tell if a data type is mobile, apply the following two tests. 

	The width test.  Must the data be moved piecemeal?  For example, on
your micro, can you move a two-byte address around as a unit, or do you have to
move each byte separately?  In your favorite language, can you read in an
array from floppy disk or paper tape using one instruction, or must you write a
loop to read the array elements individually?

	The length test.  Are intermediate sites needed to get data from one
site to another?  For example, to take the log of a number that the user types
in from a keyboard, do you have to store the number in a variable first and
then take its log, or can you just say (Log (Read)) as in Lisp?

	If the data type fails either test it is not fully mobile.  Note that
if it fails both, the effect can be multiplicative.  Moving say 3 bytes each
requiring 2 steps requires 6 steps altogether.

	One basis for classifying languages is the mobility of their data
types.  On microcomputers only bytes (and sometimes words) are mobile, and even
then often not for I/O.  Only numbers and Booleans, and sometimes strings, are
truly mobile in Basic, Fortran, and Algol.

	The major languages developed in the 50's and 60's whose structured
data types are mobile are (in order of development) Lisp, APL, and Snobol, the
respective types being lists, arrays, and strings.  Lisp and APL also have
mobile strings.  In Lisp atoms serve as strings.  In APL a vector of characters
is printed without spaces between its characters and so can play the role of a
string.  Lisp and Snobol have arrays that are not nearly as mobile as APL's,
though some implementations of Lisp come close, namely to within the ability to
read and write them from and to devices.

	In my opinion lists are preferable to arrays as a general-purpose data
type since anything that an array can represent can be conveniently represented
by a list, whereas the converse is far from true.  From the implementation (and
hence efficiency) viewpoint, arrays offer faster random access.  However, the
modern APL style of programming makes relatively light use of random access.
Moreover, as compiler optimizers get progressively "smarter," it will become
progressively harder to infer properties of the implementation from properties
of the language definition.

	For example, often the compiler has enough information to infer that a
Lisp list is being used array-style, and it can then choose to represent the
list as an array.  Conversely it may spot that an APL array would best be
implemented as a Lisp-style list, e.g. when much concatenation of APL arrays is
being performed and no random access is used.

	Lisp, APL, and Snobol all have mobile programs.  This is accomplished
by representing programs as lists (Lisp) or strings (APL, Snobol).  Each
supplies a function for running such programs: Eval in Lisp, Execute in APL,
Goto (!) in Snobol.  The program's mobility is inherited from that of its
representing medium, just as the mobility of an integer in the range -128 to
127 is inherited from the mobility of the eight-bit byte that represents it.
Mobility of Lisp programs is a central aspect of Lisp's design
philosophy, while in APL and Snobol the feature was clearly not thought throuh
in sufficient detail and in each case is hedged about with restrictions on its
use.

	Lisp goes beyond APL and Snobol by also having mobile functions.  From
a programmer's viewpoint the main difference between a program and a function
is that functions are objects that explicitly take arguments, whereas the only
way to pass information to a program is to store it, before running the
program, in variables that the program "knows" about.

	Lisp implements mobile functions by using lambda-expressions, a method
of representing functions due to the logician Alonzo Church.  For example, the
function that computes the length of a two-dimensional vector whose coordinates
are x and y could be represented with the list

	(Lambda (x y) (Sqrt (Plus (Times x x)
				  (Times y y))))

	Such an object can be read, printed, assigned to variables, passed as
an argument to another function, returned as the result of a function, and of
course applied to a pair of arguments.  To take an unusual example, running the
program (Apply (Read) (List 3 4)) would cause the function typed in response to
the Read to be applied to the list of arguments (3 4).  If the user typed in
the above lambda-expression, the result would be 5.

	The closest APL and Snobol can come to this is to have a name of a
function, say ZOT, be a datum.  To apply the function so named in APL one would
concatenate the name with the argument(s), say 3, then Execute the resulting
program "ZOT 3".  Roughly the same approach will work in Snobol.  The catch is
that names on their own mean nothing; the technique will not work if the name
is not defined, or if somebody changes its definition.  Thus if you print the
name of an APL function on a device from which you want to read it back in
later, the original definition may in the meantime change or disappear from the
workspace.  This difficulty does not arise with lambda expressions, which
contain their own definition.  Thus functions have at best limited mobility in
APL and Snobol.

	The concept of mobility was first identified by Robin Popplestone in
1968 in describing the virtues of his language POP-2.  In hindsight it is clear
that this was a concern, whether or not a subconscious one, for the designers
of Lisp, APL and Snobol.  Popplestone used the term "first-class citizen" to
refer to a mobile datum.  I prefer "mobile" as being less of a mouthful.

2.  Modularity of function

	Subroutine libraries have something that programming languages often
lack, and that is modularity of function.  One does not view a subroutine
library as a monolith but rather as a loosely coupled set of subroutines.  The
term "subset," often applied in a vague way to programming languages, has an
obvious and precise meaning for subroutine libraries.

	Lisp is just like a subroutine library.  It is no more than a set of
functions.  The user may add to this set by getting more functions from
whatever subroutine library is maintained by the local environment.  And the
user's program itself consists of a set of functions.  Any of these functions
can be invoked from the user's terminal or from the user's or any other
program.  All three kinds are invoked with identical syntax, namely

	(Function Arg1 Arg2 ... Argn).

	The conventions for representing lists, Lisp's primary structured data
type, are the same for representing programs, and since those conventions are
simple there is little to learn.

	I should add that my own preference is to program in an Algol-like
language, Cgol, which is then automatically translated to Lisp.  Despite the
regular and easily learned syntax of Lisp, I do not like having to write x+y as
(Plus x y).  I do too much mathematics to feel comfortable switching
representations in order to program.  Fortunately it is not necessary to
compromise functional modularity in order to use other syntactic conventions.

3.  Declarative Programming

	Here is an innocent looking pair of equations.

		(a+1) x b  =  a x b + b
		    0 x b  =  0

	What sets these equations apart from the millions of other equations I
could have written is that these permit me to convert any method for adding
into a method for multiplying.  Suppose for example I want to multiply 3 by 7.
Since 3 = 2+1 I can use the equation to express 3x7 as 2x7+7, reducing the
original problem to a smaller one which can be solved by the same method.
Eventually I have (((0x7+7)+7)+7), which the second equation turns into
(((0+7)+7)+7).  Using the method for adding, three times, I end up with the
desired answer.

	Turning these equations into a Lisp program to give a recursive
definition of (Times a b) is an essentially mechanical procedure yielding

	(Cond ((Zerop a) 0)
	      (T (Plus (Times (Sub1 a) b) b)))

or in the "syntactically sugared" version of Lisp referred to earlier,

	if a=0 then 0 else (a-1)*b+b.

	The significance of this example lies in the observations that (i) the
facts were so obvious it was hard to make a mistake, and (ii) the procedure for
converting those facts into something we could run as a program was so
stereotyped and straightforward (match the problem against the left hand side
of an equation, replace it by the corresponding right hand side) that again it
was hard to make a mistake.

	Programming in Lisp comes close enough to this "declarative" style to
make programming a remarkably error-free process.  A well-written Lisp program
will look (to those who can read Lisp) like a collection of facts.  The
subtlety of the program then amounts to the subtlety of the facts.  If the
facts are obvious, as with the above, there is little to explain.  If the facts
are obscure then you have a program that needs to be proved correct.

	Though the example above dealt with numbers, the mobility of Lisp's
structured data types makes it possible to apply the same method to writing
programs that operate on lists, functions, programs, and so on.

	My own research includes developing and testing new algorithms for a
variety of problems.  For the sake of ease of implementation and short
debugging time, my style is, as far as possible, to set down the facts relevant
to the computation and express them as Lisp functions.  Thanks to the quality
of the Lisp compiler used at MIT I end up with reasonably efficient programs,
in many cases as efficient as if I had adopted a more traditional style of
programming with while loops and assignments.  (One thing I miss, however, is
the ability to just write down the pure equations and have a preprocessor
automatically combine them into a single Lisp program.)

	My prime testing program referred to in Martin Gardner's Scientific
American column for August 1978 is written entirely in this style.  Some of the
facts it uses are obvious ones concerning such topics as exponentiation modulo
n.  Some of the facts however are considerably deeper and were first proved by
the well-known computer scientist Michael Rabin.

	Rewriting this particular program in some other style would achieve
little if anything in the way of efficiency.  It would however make it harder
to see the connection between the collection of facts supporting the method and
the program itself.

	This principle of executing facts as programs has encouraged people to
generalize the idea to other facts besides equations, and a series of
programming languages have evolved based on this generalization, two of the
more prominent ones being Planner and Prolog.

4.  Metalanguage

"Meta" is Greek for "about."  Lisp lists can be used, inter alia, to represent
expressions in various languages.  Thus Lisp makes an ideal metalanguage, a
language for talking about language.  As such Lisp finds application in a large
variety of areas dealing with the processing of language, as shown in the
table.

	Area			   Language
  Compiling			Parsed programs
  Algebraic Simplification	Algebraic formulas
  Natural Language		Parsed sentences
  Automatic Theorem Proving	Logical formulas
  Program Verification		Parsed programs and logical formulas
  Automatic Programming		Specifications and resulting programs
  Knowledge-Based Systems	Facts and rules

	What makes Lisp particularly well suited to these applications is that
they frequently call for operations on expressions that are best viewed
recursively as facts and procedures stated in terms of the immediate
constituents of the expressions.  This is an instance of the declarative style
described earlier, for the case when the data are expressions.

	To take an example from algebraic simplification, the derivative of an
expression can be defined in terms of the derivatives of its immediate
constituents.  Thus (Deriv '(Plus x y)) would be

	(List 'Plus (Deriv x)
		    (Deriv y))

where x and y themselves may be quite complicated algebraic expressions.
Similarly (Deriv '(Times x y)) would be

	(List 'Plus (List 'Times (Deriv x) y)
		    (List 'Times x (Deriv y)))

and so on for other operators.  From such facts it is straightforward to
construct a recursive Lisp program for differentiating algebraic expressions.

	A helpful way to think about the principle illustrated by the above is
to view the equations from which the Lisp programs are derived as dealing with
only a small region of an expression at a time.  While algebra tends to supply
particularly nice examples of this principle, the principle in one form or
another pervades essentially all areas where linguistic structures are
encountered.

Conclusion

	This discussion of Lisp has confined itself to those aspects of Lisp
directly visible to the user.  It has not considered Lisp's substantial
contributions to language implementation technology, such as garbage
collection, the interpreter/compiler dichotomy, and dynamic module linking in
place of the usually more static linking loader.  While it is difficult to
consider Lisp unique in any single one of its aspects, when looked at as a
whole Lisp stands out as a quite remarkable and original language that does
credit to its inventor, John McCarthy.